/** 
 * \file types.c
 *       Filename:  types.c
 * =====================================================================================
 * 
 *    Description:  Implementation of some functions for the management of 
 *    				OpenStreetMap data types
 * 
 *        Version:  1.0
 *        Created:  07/11/2009 18:15:49
 *       Revision:  none
 *       Compiler:  gcc
 * 
 *         Author:  François Hissel (fh), francois.hissel@m4x.org
 *        Company:  
 * 
 * =====================================================================================
 */

#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>
#include	"types.h"

/**
 * \brief Find the position where the string should be inserted in a sorted list (alphabetical order)
 *
 * This function performs a dichotomic search on the description table to look for the string given in argument. If it is found, it returns 1 and pos gets the position of the field in the description table. If not, the function returns 0 and pos gets the position of the \b previous field, which is the field where the value should be inserted in a sorted list.
 * \param description Description table in which the search shall be performed
 * \param string String to search
 * \param pos Integer reference where the position of insertion will be stored
 * \return 0 if the string is not found, 1 otherwise
 */
int _search(Description *description,char *string,int *pos) {
	if (description->number==0) {
		*pos=0;
		return 0;
	}
	unsigned char a=0;
	unsigned char b=description->number-1;
	unsigned char c;
	int cmp=strcmp(description->names[a]->name,string);
	if (cmp>=0) {
		*pos=0;
		return (cmp==0);
	}
	cmp=strcmp(description->names[b]->name,string);
	if (cmp<=0) {
		if (cmp<0) *pos=description->number; else *pos=description->number-1;
		return (cmp==0);
	}
	while (a<b-1) {
		c=(b+a)/2;
		int cmp=strcmp(description->names[c]->name,string);
		if (cmp==0) {
			*pos=c;
			return 1;
		}
		if (cmp<0) a=c; else b=c;
	}
	if (strcmp(description->names[a]->name,string)==0) {
		*pos=a;
		return 1;
	}
	if (b>a && strcmp(description->names[b]->name,string)==0) {
		*pos=b;
		return 1;
	}
	*pos=b;
	return 0;
}

Field *search(Description *description,char *string) {
	int pos;
	if (_search(description,string,&pos)==0) 
		return description->names[pos];
	else return 0;
}

Field *insert_unique(Description *description,char *string) {
	if (description->number==MAX_ATTRIBUTES) return 0;
	int pos;
	int found=_search(description,string,&pos);
	if (found) return description->names[pos];
	unsigned char i;
	for (i=description->number;i>pos;--i) description->names[i]=description->names[i-1];
	Field *new_field=(Field*)malloc(sizeof(Field));
	int size=strlen(string)+1;
	new_field->name=(char*)malloc(size);
	memcpy(new_field->name,string,size);
	new_field->position=description->number;
	description->names[pos]=new_field;
	description->number++;
	return new_field;
}

Node *find_node(Node **list,int size,unsigned long id) {
	int a=0;
	int b=size-1;
	while (b>a+1) {
		int c=(a+b)/2;
		if (list[c]->id==id) return list[c]; else if (list[c]->id<id) a=c; else b=c;
	}
	if (list[a]->id==id) return list[a];
	if (list[b]->id==id) return list[b];
	return 0;
}

/**
 * \brief Sort a part of a list, base function of the quick-sort algorithm
 *
 * This function sorts a part of a list of nodes, starting at node 'nodes', with the size given as the second argument. At the end of the call, head will be the new head of the list section (which may have changed during the sorting) and tail will be the last node of the list section. These two return values are used to merge two lists at the end ot the algorithm.
 * \param nodes Start of the list section
 * \param size Number of nodes of the section which has to be sorted
 * \param head The value at the start of the function is ignored and shall not hold a pointer to an allocated region of the memory. At the end, head holds a reference to the pointer at the new beginning of the list section.
 * \param tail The value at the start of the function is ignored and shall not hold a pointer to an allocated region of the memory. At the end, tail holds a reference to the pointer on the last element of the new list section.
 */
void sort_nodes_rec(Nodes *nodes,int size,Nodes **head,Nodes **tail) {
	if (size<=1) {
		*head=nodes;
		*tail=nodes;
		return;
	}
	Nodes *cur,*cura,*curb,*thead,*ttail,*end;
	sort_nodes_rec(nodes,size/2,head,&thead);
	sort_nodes_rec(thead->next,size-size/2,tail,&ttail);
	thead->next=*tail;
	cura=*head;
	curb=*tail;
	if (cura->node->id>curb->node->id) {
		*head=curb;
		curb=curb->next;
	} else cura=cura->next;	
	cur=*head;
	end=ttail->next;
	while (cura!=*tail && curb!=end) {
		if (cura->node->id<curb->node->id) {
			cur->next=cura;
			cura=cura->next;
		} else {
			cur->next=curb;
			curb=curb->next;
		}
		cur=cur->next;
	}
	if (cura==*tail) {
		cur->next=curb;
		*tail=ttail;
	} else {
		cur->next=cura;
		*tail=thead;
	}
	(*tail)->next=end;
}

int sort_nodes(Nodes *nodes,Node ***newlist) {
	int size=0;
	Nodes *cur;
	for (cur=nodes;cur;cur=cur->next) size++;
	sort_nodes_rec(nodes,size,&nodes,&cur);
	*newlist=(Node**)malloc(size*sizeof(Node*));
	int i=0;
	for (cur=nodes;cur;cur=cur->next) (*newlist)[i++]=cur->node;
	free_nodes(nodes);
	return size;
}

void free_description(Description *description) {
	size_t i;
	for (i=0;i<description->number;++i) {
		free(description->names[i]->name);
		free(description->names[i]);
	}
	free(description);
}

void free_node(Node *node) {
	size_t i;
	for (i=0;i<MAX_ATTRIBUTES;++i) if (node->attributes[i]) free(node->attributes[i]);
	free(node);
}

void free_nodes(Nodes *nodes) {
	Nodes *cur=nodes;
	while (cur!=0) {
		Nodes *prev=cur;
		cur=cur->next;
		free(prev);
	}
}

void free_way(Way *way) {
	size_t i;
	for (i=0;i<MAX_ATTRIBUTES;++i) if (way->attributes[i]) free(way->attributes[i]);
	free_nodes(way->nodes);
	free(way);
}

void free_ways(Ways *ways) {
	Ways *cur=ways;
	while (cur!=0) {
		Ways *prev=cur;
		cur=cur->next;
		free(prev);
	}
}
